package graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 邻接表
 */

public class GraphByNode {
    class Node{
        public int src;
        public int dest;
        public Node next;
        public int weight ;
        public Node(int src, int dest ,int weight) {
            this.src = src;
            this.dest = dest;

            this.weight = weight;
        }

    }
    public List<Node> edgList;
    public char[] arrayV;
    public boolean isDirect;

    public GraphByNode(int size,boolean isDirect) {
        this.edgList = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            edgList.add(null);
        }
        this.arrayV = new char[size];
        this.isDirect = isDirect;
    }

    /**
     * 初始化
     * @param array
     */
    public void initArrayV(char[] array){
        for (int i = 0; i < arrayV.length; i++) {
            arrayV[i] = array[i];
        }
    }

    /**
     * 添加边
     * @param src 起始点
     * @param dest 终点
     * @param weight 权值
     */
    public void addEdge(char src,char dest,int weight){
        int srcIndex = findIndex(src);
        int destIndex = findIndex(dest);
        addEdgeChild(srcIndex,destIndex,weight);
        //对无向图的处理

        if(!isDirect){
            addEdgeChild(destIndex,srcIndex,weight);

        }


    }

    public void addEdgeChild(int srcIndex,int destIndex,int weight){
        Node node = edgList.get(srcIndex);
        Node cur =node;
        while(cur != null){
            if(cur.dest == destIndex){
                return;
            }
            cur =  cur.next;
        }
        Node newNode = new Node(srcIndex,destIndex,weight);
        newNode.next = node;
        edgList.set(srcIndex,newNode);

    }
    public int findIndex(char x){
        for (int i = 0; i < arrayV.length; i++) {
            if(arrayV[i] == x){
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取顶点的度
     * @param v
     * @return
     */

    public int getDevOfV(char v){
        int srcIndex = findIndex(v);
        Node node = edgList.get(srcIndex);
        int count =0;
        while(node != null){
            count++;
            node = node.next;

        }
        //如果是有向图

        if(isDirect){
            for (int i = 0; i < arrayV.length; i++) {
                if(i == srcIndex){
                    continue;
                }else{
                    Node node1 = edgList.get(i);
                    while(node1 != null){
                        if(node1.dest == srcIndex) {
                            count++;
                        }
                        node1 = node1.next;
                    }


                }

            }
        }
        return count;
    }
    public void printGraph(){
        for (int i = 0; i < arrayV.length; i++) {
            Node node = edgList.get(i);
            System.out.print(arrayV[i]+ " > ");
            while(node != null){
                System.out.print(arrayV[node.dest]+ " ");
                node = node.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        GraphByNode graph = new GraphByNode(4,false);
        char[] array = {'A','B','C','D'};
        graph.initArrayV(array);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);

        System.out.println();
        System.out.println("getDevOfV:: "+graph.getDevOfV('A'));
        graph.printGraph();

    }

}
